home *** CD-ROM | disk | FTP | other *** search
/ Die Ultimative Software-P…i Collection 1996 & 1997 / Die Ultimative Software-Pakete CD-ROM fur Atari Collection 1996 & 1997.iso / g / gnu_c / gpplib22.zoo / libsrc / xbitset.cc < prev    next >
Encoding:
C/C++ Source or Header  |  1993-11-30  |  19.2 KB  |  1,001 lines
  1. /* 
  2. Copyright (C) 1988 Free Software Foundation
  3.     written by Doug Lea (dl@rocky.oswego.edu)
  4.  
  5. This file is part of the GNU C++ Library.  This library is free
  6. software; you can redistribute it and/or modify it under the terms of
  7. the GNU Library General Public License as published by the Free
  8. Software Foundation; either version 2 of the License, or (at your
  9. option) any later version.  This library is distributed in the hope
  10. that it will be useful, but WITHOUT ANY WARRANTY; without even the
  11. implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  12. PURPOSE.  See the GNU Library General Public License for more details.
  13. You should have received a copy of the GNU Library General Public
  14. License along with this library; if not, write to the Free Software
  15. Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
  16. */
  17.  
  18. /* 
  19.   BitSet class implementation
  20.  */
  21.  
  22. #ifdef __GNUG__
  23. #pragma implementation
  24. #endif
  25. #include <xbitset.h>
  26. #include <std.h>
  27. #include <limits.h>
  28. #include <xobstack.h>
  29. #include <xallocri.h>
  30. #include <new.h>
  31. #include <builtin.h>
  32. #include <string.h>
  33. #include <strstream.h>
  34.  
  35. void BitSet::error(const char* msg) const
  36. {
  37.   (*lib_error_handler)("BitSet", msg);
  38. }
  39.  
  40. //  globals & constants
  41.  
  42. BitSetRep  _nilBitSetRep = { 0, 1, 0, {0} }; // nil BitSets point here
  43.  
  44. #define ONES               ((unsigned short)(~0L))
  45. #define MAXBitSetRep_SIZE  ((1 << (sizeof(short)*CHAR_BIT - 1)) - 1)
  46. #define MINBitSetRep_SIZE  16
  47.  
  48. #ifndef MALLOC_MIN_OVERHEAD
  49. #define MALLOC_MIN_OVERHEAD     4
  50. #endif
  51.  
  52. // break things up into .s indices and positions
  53.  
  54.  
  55. // mask out bits from left
  56.  
  57. static inline unsigned short lmask(int p)
  58. {
  59.   return ONES << p;
  60. }
  61.  
  62. // mask out high bits
  63.  
  64. static inline unsigned short rmask(int p)
  65. {
  66.   return ONES >> (BITSETBITS - 1 - p);
  67. }
  68.  
  69.  
  70. inline static BitSetRep* BSnew(int newlen)
  71. {
  72.   unsigned int siz = sizeof(BitSetRep) + newlen * sizeof(short) 
  73.     + MALLOC_MIN_OVERHEAD;
  74.   unsigned int allocsiz = MINBitSetRep_SIZE;;
  75.   while (allocsiz < siz) allocsiz <<= 1;
  76.   allocsiz -= MALLOC_MIN_OVERHEAD;
  77.   if (allocsiz >= MAXBitSetRep_SIZE * sizeof(short))
  78.     (*lib_error_handler)("BitSet", "Requested length out of range");
  79.     
  80.   BitSetRep* rep = (BitSetRep *) new char[allocsiz];
  81.   memset(rep, 0, allocsiz);
  82.   rep->sz = (allocsiz - sizeof(BitSetRep) + sizeof(short)) / sizeof(short);
  83.   return rep;
  84. }
  85.  
  86. BitSetRep* BitSetalloc(BitSetRep* old, const unsigned short* src, int srclen,
  87.                 int newvirt, int newlen)
  88. {
  89.   if (old == &_nilBitSetRep) old = 0;
  90.   BitSetRep* rep;
  91.   if (old == 0 || newlen >= old->sz)
  92.     rep = BSnew(newlen);
  93.   else
  94.     rep = old;
  95.  
  96.   rep->len = newlen;
  97.   rep->virt = newvirt;
  98.  
  99.   if (srclen != 0 && src != rep->s)
  100.     memcpy(rep->s, src, srclen * sizeof(short));
  101.   // BUG fix: extend virtual bit! 20 Oct 1992 Kevin Karplus
  102.   if (rep->virt)
  103.       memset(&rep->s[srclen], ONES, (newlen - srclen) * sizeof(short));
  104.   if (old != rep && old != 0) delete old;
  105.   return rep;
  106. }
  107.  
  108. BitSetRep* BitSetresize(BitSetRep* old, int newlen)
  109. {
  110.   BitSetRep* rep;
  111.   if (old == 0 || old == &_nilBitSetRep)
  112.   {
  113.     rep = BSnew(newlen);
  114.     rep->virt = 0;
  115.   }
  116.   else if (newlen >= old->sz)
  117.   {
  118.     rep = BSnew(newlen);
  119.     memcpy(rep->s, old->s, old->len * sizeof(short));
  120.     rep->virt = old->virt;
  121.     // BUG fix: extend virtual bit!  20 Oct 1992 Kevin Karplus
  122.     if (rep->virt)
  123.     memset(&rep->s[old->len], ONES, (newlen - old->len) * sizeof(short));
  124.     delete old;
  125.   }
  126.   else
  127.     rep = old;
  128.  
  129.   rep->len = newlen;
  130.  
  131.   return rep;
  132. }
  133.  
  134. // same, for straight copy
  135.  
  136. BitSetRep* BitSetcopy(BitSetRep* old, const BitSetRep* src)
  137. {
  138.   BitSetRep* rep;
  139.   if (old == &_nilBitSetRep) old = 0;
  140.   if (src == 0 || src == &_nilBitSetRep)
  141.   {
  142.     if (old == 0)
  143.       rep = BSnew(0);
  144.     else
  145.       rep = old;
  146.     rep->len = 0;
  147.     rep->virt = 0;
  148.   }
  149.   else if (old == src) 
  150.     return old; 
  151.   else 
  152.   {
  153.     int newlen = src->len;
  154.     if (old == 0 || newlen > old->sz)
  155.     {
  156.       rep = BSnew(newlen);
  157.       if (old != 0) delete old;
  158.     }
  159.     else
  160.       rep = old;
  161.  
  162.     memcpy(rep->s, src->s, newlen * sizeof(short));
  163.     rep->len = newlen;
  164.     rep->virt = src->virt;
  165.   }
  166.   return rep;
  167. }
  168.  
  169.  
  170. // remove unneeded top bits
  171.  
  172. inline static void trim(BitSetRep* rep)
  173. {
  174.   int l = rep->len;
  175.   unsigned short* s = &(rep->s[l - 1]);
  176.  
  177.   if (rep->virt == 0)
  178.     while (l > 0 && *s-- == 0) --l;
  179.   else
  180.     while (l > 0 && *s-- == ONES) --l;
  181.   rep->len = l;
  182. }
  183.  
  184. int operator == (const BitSet& x, const BitSet& y)
  185. {
  186.   if (x.rep->virt != y.rep->virt)
  187.     return 0;
  188.   int xl = x.rep->len;
  189.   int yl = y.rep->len;
  190.  
  191.   unsigned short* xs = x.rep->s;
  192.   unsigned short* ys = y.rep->s;
  193.   if (xl<=yl)
  194.     {
  195.       if (memcmp((void*)xs, (void*)ys, xl * sizeof(short)))
  196.       return 0;
  197.       for (register int i=xl; i<yl; i++)
  198.         if (ys[i])
  199.       return 0;
  200.       return 1;
  201.     }
  202.   else
  203.     {
  204.       if (memcmp((void*)xs, (void*)ys, yl * sizeof(short)))
  205.       return 0;
  206.       for (register int i=yl; i<xl; i++)
  207.         if (xs[i]) 
  208.       return 0;
  209.       return 1;
  210.     }
  211. }
  212.  
  213. int operator <= (const BitSet& x, const BitSet& y)
  214. {
  215.   if (x.rep->virt > y.rep->virt)
  216.     return 0;
  217.  
  218.   int xl = x.rep->len;
  219.   int yl = y.rep->len; 
  220.  
  221.   unsigned short* xs = x.rep->s;
  222.   unsigned short* ys = y.rep->s;
  223.   unsigned short* topx = &(xs[xl]);
  224.   unsigned short* topy = &(ys[yl]);
  225.  
  226.   while (xs < topx && ys < topy)
  227.   {
  228.     unsigned short a = *xs++;
  229.     unsigned short b = *ys++;
  230.     if ((a | b) != b)
  231.       return 0;
  232.   }
  233.   if (xl == yl)
  234.     return x.rep->virt <= y.rep->virt;
  235.   else if (xl < yl)
  236.     return !x.rep->virt;
  237.   else
  238.     return y.rep->virt;
  239. }
  240.  
  241.  
  242. int operator < (const BitSet& x, const BitSet& y)
  243. {
  244.   if (x.rep->virt > y.rep->virt)
  245.     return 0;
  246.  
  247.   int xl = x.rep->len;
  248.   int yl = y.rep->len;
  249.  
  250.   unsigned short* xs = x.rep->s;
  251.   unsigned short* ys = y.rep->s;
  252.   unsigned short* topx = &(xs[xl]);
  253.   unsigned short* topy = &(ys[yl]);
  254.   int one_diff = 0;
  255.   while (xs < topx && ys < topy)
  256.   {
  257.     unsigned short a = *xs++;
  258.     unsigned short b = *ys++;
  259.     unsigned short c = a | b;
  260.     if (c != b)
  261.       return 0;
  262.     else if (c != a)
  263.       one_diff = 1;
  264.   }
  265.   if (xl == yl)
  266.     return x.rep->virt < y.rep->virt || 
  267.       (one_diff && x.rep->virt == y.rep->virt);
  268.   else if (xl < yl)
  269.     return !x.rep->virt;
  270.   else
  271.     return y.rep->virt;
  272. }
  273.  
  274.  
  275.  
  276. int BitSet::empty() const
  277. {
  278.   if (rep->virt == 1)
  279.     return 0;
  280.  
  281.   unsigned short* bots = rep->s;
  282.   unsigned short* s = &(bots[rep->len - 1]);
  283.   while (s >= bots) if (*s-- != 0) return 0;
  284.   return 1;
  285. }
  286.  
  287.  
  288. int BitSet::count(int b) const
  289. {
  290.   if (b == rep->virt)
  291.     return -1;
  292.   int l = 0;
  293.   unsigned short* s = rep->s;
  294.   unsigned short* tops = &(s[rep->len]);
  295.   if (b == 1)
  296.   {
  297.     while (s < tops)
  298.     {
  299.       unsigned short a = *s++;
  300.       for (int i = 0; i < BITSETBITS && a != 0; ++i)
  301.       {
  302.         if (a & 1)
  303.           ++l;
  304.         a >>= 1;
  305.       }
  306.     }
  307.   }
  308.   else
  309.   {
  310.     unsigned short maxbit = 1 << (BITSETBITS - 1);
  311.     while (s < tops)
  312.     {
  313.       unsigned short a = *s++;
  314.       for (int i = 0; i < BITSETBITS; ++i)
  315.       {
  316.         if ((a & maxbit) == 0)
  317.           ++l;
  318.         a <<= 1;
  319.       }
  320.     }
  321.   }
  322.   return l;
  323. }
  324.  
  325. BitSetRep* BitSetcmpl(const BitSetRep* src, BitSetRep* r)
  326. {
  327.   r = BitSetcopy(r, src);
  328.   r->virt = !src->virt;
  329.   unsigned short* rs = r->s;
  330.   unsigned short* topr = &(rs[r->len]);
  331.   if (r->len == 0)
  332.     *rs = ONES;
  333.   else
  334.   {
  335.     while (rs < topr)
  336.     {
  337.       unsigned short cmp = ~(*rs);
  338.       *rs++ = cmp;
  339.     }
  340.   }
  341.   trim(r);
  342.   return r;
  343. }
  344.  
  345.  
  346. BitSetRep* BitSetop(const BitSetRep* x, const BitSetRep* y, 
  347.                     BitSetRep* r, char op)
  348. {
  349.   int xrsame = x == r;
  350.   int yrsame = y == r;
  351.   int xv = x->virt;
  352.   int yv = y->virt;
  353.   int xl = x->len;
  354.   int yl = y->len;
  355.   int rl = (xl >= yl)? xl : yl;
  356.  
  357.   r = BitSetresize(r, rl);
  358.   unsigned short* rs = r->s;
  359.   unsigned short* topr = &(rs[rl]);
  360.  
  361.   int av, bv;
  362.   const unsigned short* as;
  363.   const unsigned short* topa;
  364.   const unsigned short* bs;
  365.   const unsigned short* topb;
  366.   
  367.   if (xl <= yl)
  368.   {
  369.     as = (xrsame)? r->s : x->s;
  370.     av = xv;
  371.     topa = &(as[xl]);
  372.     bs = (yrsame)? r->s : y->s;
  373.     bv = yv;
  374.     topb = &(bs[yl]);
  375.   }
  376.   else
  377.   {
  378.     as = (yrsame)? r->s : y->s;
  379.     av = yv;
  380.     topa = &(as[yl]);
  381.     bs = (xrsame)? r->s : x->s;
  382.     bv = xv;
  383.     topb = &(bs[xl]);
  384.     if (op == '-')              // reverse sense of difference
  385.       op = 'D';
  386.   }
  387.  
  388.   switch (op)
  389.   {
  390.   case '&':
  391.     r->virt = av & bv;
  392.     while (as < topa) *rs++ = *as++ & *bs++;
  393.     if (av)
  394.       while (rs < topr) *rs++ = *bs++;
  395.     else
  396.       while (rs < topr) *rs++ = 0;
  397.     break;
  398.   case '|':
  399.     r->virt = av | bv;
  400.     while (as < topa) *rs++ = *as++ | *bs++;
  401.     if (av)
  402.       while (rs < topr) *rs++ = ONES;
  403.     else
  404.       while (rs < topr) *rs++ = *bs++;
  405.     break;
  406.   case '^':
  407.     r->virt = av ^ bv;
  408.     while (as < topa) *rs++ = *as++ ^ *bs++;
  409.     if (av)
  410.       while (rs < topr) *rs++ = ~(*bs++);
  411.     else
  412.       while (rs < topr) *rs++ = *bs++;
  413.     break;
  414.   case '-':
  415.     r->virt = av & ~(bv);
  416.     while (as < topa) *rs++ = *as++ & ~(*bs++);
  417.     if (av)
  418.       while (rs < topr) *rs++ = ~(*bs++);
  419.     else
  420.       while (rs < topr) *rs++ = 0;
  421.     break;
  422.   case 'D':
  423.     r->virt = ~(av) & (bv);
  424.     while (as < topa) *rs++ = ~(*as++) & (*bs++);
  425.     if (av)
  426.       while (rs < topr) *rs++ = 0;
  427.     else
  428.       while (rs < topr) *rs++ = *bs++;
  429.     break;
  430.   }
  431.   trim(r);
  432.   return r;
  433. }
  434.  
  435.  
  436. void BitSet::set(int p)
  437. {
  438.   if (p < 0) error("Illegal bit index");
  439.  
  440.   int index = BitSet_index(p);
  441.   int pos   = BitSet_pos(p);
  442.  
  443.   if (index >= rep->len)
  444.   {
  445.     if (rep->virt)
  446.       return;
  447.     else
  448.       rep = BitSetresize(rep, index+1);
  449.   }
  450.  
  451.   rep->s[index] |= (1 << pos);
  452. }
  453.  
  454. void BitSet::clear()
  455. {
  456.   if (rep->len > 0) memset(rep->s, 0, rep->sz * sizeof(short));
  457.   rep->len = rep->virt = 0;
  458. }
  459.  
  460. void BitSet::clear(int p)
  461. {
  462.   if (p < 0) error("Illegal bit index");
  463.   int index = BitSet_index(p);
  464.   if (index >= rep->len)
  465.   {
  466.     if (rep->virt == 0)
  467.       return;
  468.     else
  469.       rep = BitSetresize(rep, index+1);
  470.   }
  471.   rep->s[index] &= ~(1 << BitSet_pos(p));
  472. }
  473.  
  474. void BitSet::invert(int p)
  475. {
  476.   if (p < 0) error("Illegal bit index");
  477.   int index = BitSet_index(p);
  478.   if (index >= rep->len) rep = BitSetresize(rep, index+1);
  479.   rep->s[index] ^= (1 << BitSet_pos(p));
  480. }
  481.  
  482. void BitSet::set(int from, int to)
  483. {
  484.   if (from < 0 || from > to) error("Illegal bit index");
  485.  
  486.   int index1 = BitSet_index(from);
  487.   int pos1   = BitSet_pos(from);
  488.   
  489.   if (rep->virt && index1 >= rep->len)
  490.     return;
  491.  
  492.   int index2 = BitSet_index(to);
  493.   int pos2   = BitSet_pos(to);
  494.  
  495.   if (index2 >= rep->len)
  496.     rep = BitSetresize(rep, index2+1);
  497.  
  498.   unsigned short* s = &(rep->s[index1]);
  499.   unsigned short m1 = lmask(pos1);
  500.   unsigned short m2 = rmask(pos2);
  501.   if (index2 == index1)
  502.     *s |= m1 & m2;
  503.   else
  504.   {
  505.     *s++ |= m1;
  506.     unsigned short* top = &(rep->s[index2]);
  507.     *top |= m2;
  508.     while (s < top)
  509.       *s++ = ONES;
  510.   }
  511. }
  512.  
  513. void BitSet::clear(int from, int to)
  514. {
  515.   if (from < 0 || from > to) error("Illegal bit index");
  516.  
  517.   int index1 = BitSet_index(from);
  518.   int pos1   = BitSet_pos(from);
  519.   
  520.   if (!rep->virt && index1 >= rep->len)
  521.     return;
  522.  
  523.   int index2 = BitSet_index(to);
  524.   int pos2   = BitSet_pos(to);
  525.  
  526.   if (index2 >= rep->len)
  527.     rep = BitSetresize(rep, index2+1);
  528.  
  529.   unsigned short* s = &(rep->s[index1]);
  530.   unsigned short m1 = lmask(pos1);
  531.   unsigned short m2 = rmask(pos2);
  532.   if (index2 == index1)
  533.     *s &= ~(m1 & m2);
  534.   else
  535.   {
  536.     *s++ &= ~m1;
  537.     unsigned short* top = &(rep->s[index2]);
  538.     *top &= ~m2;
  539.     while (s < top)
  540.       *s++ = 0;
  541.   }
  542. }
  543.  
  544. void BitSet::invert(int from, int to)
  545. {
  546.   if (from < 0 || from > to) error("Illegal bit index");
  547.  
  548.   int index1 = BitSet_index(from);
  549.   int pos1   = BitSet_pos(from);
  550.   int index2 = BitSet_index(to);
  551.   int pos2   = BitSet_pos(to);
  552.  
  553.   if (index2 >= rep->len)
  554.     rep = BitSetresize(rep, index2+1);
  555.  
  556.   unsigned short* s = &(rep->s[index1]);
  557.   unsigned short m1 = lmask(pos1);
  558.   unsigned short m2 = rmask(pos2);
  559.   if (index2 == index1)
  560.     *s ^= m1 & m2;
  561.   else
  562.   {
  563.     *s++ ^= m1;
  564.     unsigned short* top = &(rep->s[index2]);
  565.     *top ^= m2;
  566.     while (s < top)
  567.     {
  568.       unsigned short cmp = ~(*s);
  569.       *s++ = cmp;
  570.     }
  571.   }
  572. }
  573.  
  574.  
  575. int BitSet::test(int from, int to) const
  576. {
  577.   if (from < 0 || from > to) return 0;
  578.  
  579.   int index1 = BitSet_index(from);
  580.   int pos1   = BitSet_pos(from);
  581.   
  582.   if (index1 >= rep->len)
  583.     return rep->virt;
  584.  
  585.   int index2 = BitSet_index(to);
  586.   int pos2   = BitSet_pos(to);
  587.  
  588.   if (index2 >= rep->len)
  589.   {
  590.     if (rep->virt)
  591.       return 1;
  592.     else 
  593.     {
  594.       index2 = rep->len - 1;
  595.       pos2 = BITSETBITS - 1;
  596.     }
  597.   }
  598.  
  599.   unsigned short* s = &(rep->s[index1]);
  600.   unsigned short m1 = lmask(pos1);
  601.   unsigned short m2 = rmask(pos2);
  602.  
  603.   if (index2 == index1)
  604.     return (*s & m1 & m2) != 0;
  605.   else
  606.   {
  607.     if (*s++ & m1)
  608.       return 1;
  609.     unsigned short* top = &(rep->s[index2]);
  610.     if (*top & m2)
  611.       return 1;
  612.     while (s < top)
  613.       if (*s++ != 0) 
  614.         return 1;
  615.     return 0;
  616.   }
  617. }
  618.  
  619. int BitSet::next(int p, int b) const
  620. {
  621.   ++p;
  622.   int index = BitSet_index(p);
  623.   int pos   = BitSet_pos(p);
  624.  
  625.   int l = rep->len;
  626.   
  627.   if (index >= l)
  628.   {
  629.     if (rep->virt == b)
  630.       return p;
  631.     else
  632.       return -1;
  633.   }
  634.   int j = index;
  635.   unsigned short* s = rep->s;
  636.   unsigned short a = s[j] >> pos;
  637.   int i = pos;
  638.  
  639.   if (b == 1)
  640.   {
  641.     for (; i < BITSETBITS && a != 0; ++i)
  642.     {
  643.       if (a & 1)
  644.         return j * BITSETBITS + i;
  645.       a >>= 1;
  646.     }
  647.     for (++j; j < l; ++j)
  648.     {
  649.       a = s[j];
  650.       for (i = 0; i < BITSETBITS && a != 0; ++i)
  651.       {
  652.         if (a & 1)
  653.           return j * BITSETBITS + i;
  654.         a >>= 1;
  655.       }
  656.     }
  657.     if (rep->virt)
  658.       return j * BITSETBITS;
  659.     else
  660.       return -1;
  661.   }
  662.   else
  663.   {
  664.     for (; i < BITSETBITS; ++i)
  665.     {
  666.       if ((a & 1) == 0)
  667.         return j * BITSETBITS + i;
  668.       a >>= 1;
  669.     }
  670.     for (++j; j < l; ++j)
  671.     {
  672.       a = s[j];
  673.       if (a != ONES)
  674.       {
  675.         for (i = 0; i < BITSETBITS; ++i)
  676.         {
  677.           if ((a & 1) == 0)
  678.             return j * BITSETBITS + i;
  679.           a >>= 1;
  680.         }
  681.       }
  682.     }
  683.     if (!rep->virt)
  684.       return j * BITSETBITS;
  685.     else
  686.       return -1;
  687.   }
  688. }
  689.  
  690. int BitSet::prev(int p, int b) const
  691. {
  692.   if (--p < 0)
  693.     return -1;
  694.  
  695.   int index = BitSet_index(p);
  696.   int pos   = BitSet_pos(p);
  697.  
  698.   unsigned short* s = rep->s;
  699.   int l = rep->len;
  700.  
  701.   if (index >= l)
  702.   {
  703.     if (rep->virt == b)
  704.       return p;
  705.     else
  706.     {
  707.       index = l - 1;
  708.       pos = BITSETBITS - 1;
  709.     }
  710.   }
  711.  
  712.   int j = index;
  713.   unsigned short a = s[j];
  714.  
  715.   int i = pos;
  716.   unsigned short maxbit = 1 << pos;
  717.  
  718.   if (b == 1)
  719.   {
  720.     for (; i >= 0 && a != 0; --i)
  721.     {
  722.       if (a & maxbit)
  723.         return j * BITSETBITS + i;
  724.       a <<= 1;
  725.     }
  726.     maxbit = 1 << (BITSETBITS - 1);
  727.     for (--j; j >= 0; --j)
  728.     {
  729.       a = s[j];
  730.       for (i = BITSETBITS - 1; i >= 0 && a != 0; --i)
  731.       {
  732.         if (a & maxbit)
  733.           return j * BITSETBITS + i;
  734.         a <<= 1;
  735.       }
  736.     }
  737.     return -1;
  738.   }
  739.   else
  740.   {
  741.     if (a != ONES)
  742.     {
  743.       for (; i >= 0; --i)
  744.       {
  745.         if ((a & maxbit) == 0)
  746.           return j * BITSETBITS + i;
  747.         a <<= 1;
  748.       }
  749.     }
  750.     maxbit = 1 << (BITSETBITS - 1);
  751.     for (--j; j >= 0; --j)
  752.     {
  753.       a = s[j];
  754.       if (a != ONES)
  755.       {
  756.         for (i = BITSETBITS - 1; i >= 0; --i)
  757.         {
  758.           if ((a & maxbit) == 0)
  759.             return j * BITSETBITS + i;
  760.           a <<= 1;
  761.         }
  762.       }
  763.     }
  764.     return -1;
  765.   }
  766. }
  767.  
  768. int BitSet::last(int b) const
  769. {
  770.   if (b == rep->virt)
  771.     return -1;
  772.   else
  773.     return prev((rep->len) * BITSETBITS, b);
  774. }
  775.  
  776.  
  777. extern AllocRing _libgxx_fmtq;
  778.  
  779. const char* BitSettoa(const BitSet& x, char f, char t, char star)
  780. {
  781.   trim(x.rep);
  782.   size_t wrksiz = (x.rep->len + 1) * BITSETBITS + 2;
  783.   char* fmtbase = (char *) _libgxx_fmtq.alloc(wrksiz);
  784.   ostrstream stream(fmtbase, wrksiz);
  785.   
  786.   x.printon(stream, f, t, star);
  787.   stream << ends;
  788.   return fmtbase;
  789. }
  790.  
  791. #if defined(__GNUG__) && !defined(NO_NRV)
  792.  
  793. BitSet shorttoBitSet(unsigned short w) return r
  794. {
  795.   r.rep = BitSetalloc(0, &w, 1, 0, 2);  trim(r.rep);
  796. }
  797.  
  798. BitSet longtoBitSet(unsigned long w) return r;
  799. {
  800.   unsigned short u[2];
  801.   u[0] = w & ((unsigned short)(~(0)));
  802.   u[1] = w >> BITSETBITS;
  803.   r.rep = BitSetalloc(0, &u[0], 2, 0, 3);
  804.   trim(r.rep);
  805. }
  806.  
  807. BitSet atoBitSet(const char* s, char f, char t, char star) return r
  808. {
  809.   int sl = strlen(s);
  810.   if (sl != 0)
  811.   {
  812.     r.rep = BitSetresize(r.rep, sl / BITSETBITS + 1);
  813.     unsigned short* rs = r.rep->s;
  814.     unsigned short a = 0;
  815.     unsigned short m = 1;
  816.     char lastch = 0;
  817.     unsigned int i = 0;
  818.     unsigned int l = 1;
  819.     for(;;)
  820.     {
  821.       char ch = s[i];
  822.       if (ch == t)
  823.         a |= m;
  824.       else if (ch == star)
  825.       {
  826.         if (r.rep->virt = lastch == t)
  827.           *rs = a | ~(m - 1);
  828.         else
  829.           *rs = a;
  830.         break;
  831.       }
  832.       else if (ch != f)
  833.       {
  834.         *rs = a;
  835.         break;
  836.       }
  837.       lastch = ch;
  838.       if (++i == sl)
  839.       {
  840.         *rs = a;
  841.         break;
  842.       }
  843.       else if (i % BITSETBITS == 0)
  844.       {
  845.         *rs++ = a;
  846.         a = 0;
  847.         m = 1;
  848.         ++l;
  849.       }
  850.       else
  851.         m <<= 1;
  852.     }
  853.     r.rep->len = l;
  854.     trim(r.rep);
  855.   }
  856.   return;
  857. }
  858.  
  859. #else
  860.  
  861. BitSet shorttoBitSet(unsigned short w) 
  862. {
  863.   BitSet r;
  864.   r.rep = BitSetalloc(0, &w, 1, 0, 2);  trim(r.rep);
  865.   return r;
  866. }
  867.  
  868. BitSet longtoBitSet(unsigned long w)
  869. {
  870.   BitSet r;
  871.   unsigned short u[2];
  872.   u[0] = w & ((unsigned short)(~(0)));
  873.   u[1] = w >> BITSETBITS;
  874.   r.rep = BitSetalloc(0, &u[0], 2, 0, 3);
  875.   trim(r.rep);
  876.   return r;
  877. }
  878.  
  879. BitSet atoBitSet(const char* s, char f, char t, char star) 
  880. {
  881.   BitSet r;
  882.   int sl = strlen(s);
  883.   if (sl != 0)
  884.   {
  885.     r.rep = BitSetresize(r.rep, sl / BITSETBITS + 1);
  886.     unsigned short* rs = r.rep->s;
  887.     unsigned short a = 0;
  888.     unsigned short m = 1;
  889.     char lastch = 0;
  890.     unsigned int i = 0;
  891.     unsigned int l = 1;
  892.     for(;;)
  893.     {
  894.       char ch = s[i];
  895.       if (ch == t)
  896.         a |= m;
  897.       else if (ch == star)
  898.       {
  899.         if (r.rep->virt = lastch == t)
  900.           *rs = a | ~(m - 1);
  901.         else
  902.           *rs = a;
  903.         break;
  904.       }
  905.       else if (ch != f)
  906.       {
  907.         *rs = a;
  908.         break;
  909.       }
  910.       lastch = ch;
  911.       if (++i == sl)
  912.       {
  913.         *rs = a;
  914.         break;
  915.       }
  916.       else if (i % BITSETBITS == 0)
  917.       {
  918.         *rs++ = a;
  919.         a = 0;
  920.         m = 1;
  921.         ++l;
  922.       }
  923.       else
  924.         m <<= 1;
  925.     }
  926.     r.rep->len = l;
  927.     trim(r.rep);
  928.   }
  929.   return r;
  930. }
  931.  
  932. #endif
  933.  
  934. ostream& operator << (ostream& s, const BitSet& x)
  935. {
  936.   if (s.opfx())
  937.     x.printon(s);
  938.   return s;
  939. }
  940.  
  941. void BitSet::printon(ostream& os, char f, char t, char star) const
  942. // FIXME:  Does not respect s.width()!
  943. {
  944.   trim(rep);
  945.   register streambuf* sb = os.rdbuf();
  946.   const unsigned short* s = rep->s;
  947.   const unsigned short* top = &(s[rep->len - 1]);
  948.  
  949.   while (s < top)
  950.   {
  951.     unsigned short a = *s++;
  952.     for (int j = 0; j < BITSETBITS; ++j)
  953.     {
  954.       sb->sputc((a & 1)? t : f);
  955.       a >>= 1;
  956.     }
  957.   }
  958.  
  959.   if (!rep->virt)
  960.   {
  961.     unsigned short a = *s;
  962.     if (rep->len != 0)
  963.     {
  964.       for (int j = 0; j < BITSETBITS && a != 0; ++j)
  965.       {
  966.         sb->sputc((a & 1)? t : f);
  967.         a >>= 1;
  968.       }
  969.     }
  970.     sb->sputc(f);
  971.   }
  972.   else
  973.   {
  974.     unsigned short a = *s;
  975.     unsigned short mask = ONES;
  976.     unsigned short himask = (1 << (BITSETBITS - 1)) - 1;
  977.     if (rep->len != 0)
  978.     {
  979.       for (int j = 0; j < BITSETBITS && a != mask; ++j)
  980.       {
  981.         sb->sputc((a & 1)? t : f);
  982.         a = (a >> 1) & himask;
  983.         mask = (mask >> 1) & himask;
  984.       }
  985.     }
  986.     sb->sputc(t);
  987.   }
  988.  
  989.   sb->sputc(star);
  990. }
  991.  
  992. int BitSet::OK() const
  993. {
  994.   int v = rep != 0;             // have a rep
  995.   v &= rep->len <= rep->sz;     // within bounds
  996.   v &= rep->virt == 0 || rep->virt == 1; // valid virtual bit
  997.   if (!v) error("invariant failure");
  998.   return v;
  999. }
  1000.  
  1001.